#include <set>
#include <iostream>

using std::set;
using std::cout;

struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int val) : val(val), next(nullptr) {}
};

class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        // 方法1：用额外的空间来做
        set<ListNode*> s;

        ListNode* curA = headA;
        ListNode* curB = headB;

        while (curA != nullptr)
        {
            s.insert(curA);
            curA = curA->next;
        }

        while (curB != nullptr)
        {
            if(s.count(curB)) return curB;
        }
        return nullptr;
    }



    ListNode *getIntersectionNode2(ListNode *headA, ListNode *headB)
    {
        // 方法2：计算A，B长度
        ListNode* curA = headA;
        ListNode* curB = headB;

        int ListALen = 0;
        int ListBLen = 0;

        while (curA)
        {
            ++ ListALen;
            curA = curA->next;
        }

        while (curB)
        {
            ++ ListBLen;
            curB = curB->next;
        }

        curA = headA;
        curB = headB;
        int len;
        if(curA > curB)
        {
            len = curA - curB;

            while (-- len >= 0)
            {
                curA = curA->next;
            }
        }
        else
        {
            len = curB - curA;

            while (-- len >= 0)
            {
                curB = curB->next;
            }
        }

        while (curA != nullptr)
        {
            if(curA != curB)
            {
                curA = curA->next;
                curB = curB->next;
            }
            else
            {
                return curA;
            }
        }
        return nullptr;
    }
};